package com.cty._04_Optimization._52_FirstCommonNodeInLists;

/**
 * @Auther: cty
 * @Date: 2020/7/21 10:40
 * @Description: 面试题52：两个链表的第一个公共结点
 * 题目：输入两个链表，找出它们的第一个公共结点。
 * @version: 1.0
 */
public class FirstCommonNodeInLists {

    public static ListNode firstCommonNodeInLists(ListNode listA, ListNode listB){
        if(listA==null || listB==null)
            return null;

        int listALength = 0;
        ListNode currentA = listA;
        while(currentA != null){
            listALength++;
            currentA = currentA.next;
        }
        int listBLength = 0;
        ListNode currentB = listB;
        while(currentB != null){
            listBLength++;
            currentB = currentB.next;
        }

        if(listALength > listBLength){
            for(int i=0; i<listALength-listBLength; i++)
                listA = listA.next;
        }else if(listBLength > listALength){
            for(int i=0; i<listBLength-listALength; i++)
                listB = listB.next;
        }

        while(listA!=null && listB!=null){
            if(listA.key == listB.key)
                return listA;

            listA = listA.next;
            listB = listB.next;
        }

        return null;
    }  // end firstCommonNodeInLists()

}  // end class

class ListNode {
    int key;
    ListNode next;

    public ListNode(){}

    public ListNode(int key){this.key = key;}
}  // end ListNode
